package oj;

public class LC1137 {
    //矩阵快速幂
    public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1 || n==2) return 1;
        int[][] ans={
                {1,0,0},
                {0,1,0},
                {0,0,1}
        };
        int[][] ret={
                {1,1,1},
                {1,0,0},
                {0,1,0}
        };
        int k=n-2;
        while(k!=0){
            if((k&1)!=0){
                ans=mul(ret,ans);
            }
            ret=mul(ret,ret);
            k/=2;
        }
        return ans[0][0]+ans[0][1];//最终再与矩阵[f(2)相乘，结果就是矩阵ans[0][0],[0][1]位置之和
                                             //f(1)
                                             //f(0)]
    }
    private int[][] mul(int[][] a,int[][] b){
        int N=3;
        int[][] c=new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                c[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j]+a[i][2]*b[2][j];
            }
        }
        return c;
    }
    //打表法
//    static int[] arr=new int[38];
//   static{
//       arr[0]=0;
//       arr[1]=1;
//       arr[2]=1;
//       for(int i=3;i<arr.length;i++){
//           arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
//       }
//   }
//    public int tribonacci(int n) {
//        return arr[n];
//    }
}
